package com.dyz.LeetCodeforSwordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/7/3 16:35
 * @description:
 */
public class IsBalanced55 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
        node2.left = node3;
        node2.right = node4;
        root.left = node1;
        root.right = node2;
        boolean balanced = new IsBalanced55().isBalanced(root);
        System.out.println(balanced);

    }
//    // 自顶向下的递归
//    public boolean isBalanced(TreeNode root) {
//        if (root == null) {
//            return true;
//        } else {
//            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
//        }
//    }
//
//    public int height(TreeNode root) {
//        if (root == null) {
//            return 0;
//        } else {
//            return Math.max(height(root.left), height(root.right)) + 1;
//        }
//    }

    //自底向上递归.
    public boolean isBalanced(TreeNode root) {
        if(root==null){return true;}
        return height1(root)>=0;
    }
    private int height1(TreeNode root){
        if(root==null){
            return 0;
        }
        //计算左右节点的高度,当子节点不是平衡树，值为-1， 其他为其子树高度
        int left = height1(root.left);
        int right = height1(root.right);
        if(left==-1||right==-1||Math.abs(left - right)>1){
            return -1;
        }
        //左右子树取最大值 ，然后加上本身占的高度 +1
        return Math.max(left, right) + 1;
    }
}
